package datastructure.maxheap;


import java.util.Collection;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

/**
 * @author XY
 * @version 1.0.0
 * @ClassName Solution.java
 * @createTime 2021年12月07日 19:07:00
 */
public class Solution {

    //查询数组中最小的k个数
    public static int[] getLeastNumbers(int[] arr, int k) {
        //定义最大堆
//        PriorityQueue<Integer> pq = new PriorityQueue<>();
        PriorityQueue<Integer> pq = new PriorityQueue(Collections.reverseOrder());
        //先往堆中加入k个元素，入队操作会将最大的值放在第一位，剩下的元素只要与堆中最大的那个元素进行比较即可
        for(int i =0; i < k;i++){
            pq.add(arr[i]);
        }
        //进行比较，如果数组中剩下的元素比堆中最大的元素要小的话就替换元素，这里用出队和入队代替交换操作
        for(int i = k;i <arr.length;i++){
            if(!pq.isEmpty() && arr[i]<pq.peek()){
                //出队会重新排列堆中的顺序
                pq.remove();
                //入队会重新排列堆中的顺序
                pq.add(arr[i]);
            }
        }
        //比较完成之后将堆中元素赋值到新数组即可
        int[] res = new int[k];
        for(int i =0; i < k; i++){
            res[i] = pq.poll();
        }
        return res;
    }

    //查询数组中最大的k个数
    public static int[] getFeastNumbers(int[] arr, int k) {
        //定义最小堆
        MinHeap<Integer> minHeap = new MinHeap();
        //先往堆中加入k个元素，入队操作会将最小的值放在第一位，剩下的元素只要与堆中最小的那个元素进行比较即可
        for(int i =0; i < k;i++){
            minHeap.add(arr[i]);
        }
        //进行比较，如果数组中剩下的元素比堆中最小的元素要大的话就替换元素，这里用出队和入队代替交换操作
        for(int i = k;i <arr.length;i++){
            if(!minHeap.isEmpty() && arr[i] > minHeap.findMin()){
                //出队会重新排列堆中的顺序
                minHeap.extractMin();
                //入队会重新排列堆中的顺序
                minHeap.add(arr[i]);
            }
        }
        //比较完成之后将堆中元素赋值到新数组即可
        int[] res = new int[k];
        for(int i =0; i < k; i++){
            res[i] = minHeap.extractMin();
        }
        return res;
    }

    //查询数组中第k大的元素
    public static Integer findKthLargest(int[] arr, int k) {
        //定义最小堆
//        MinHeap<Integer> minHeap = new MinHeap();
        //java原生优先队列
        PriorityQueue<Integer> minHeap = new PriorityQueue();

        //先往堆中加入k个元素，入队操作会将最小的值放在第一位，剩下的元素只要与堆中最小的那个元素进行比较即可
        for(int i =0; i < k;i++){
            minHeap.add(arr[i]);
        }
        //进行比较，如果数组中剩下的元素比堆中最小的元素要大的话就替换元素，这里用出队和入队代替交换操作
        for(int i = k;i <arr.length;i++){
            if(!minHeap.isEmpty() && arr[i] > minHeap.peek()){
                //出队会重新排列堆中的顺序
                minHeap.remove();
                //入队会重新排列堆中的顺序
                minHeap.add(arr[i]);
            }
        }
        //直接返回堆根节点元素即可
        return minHeap.peek();
    }



    public static void main(String[] args) {
        int[] arr= {3,2,1};
        int[] leastNumbers = getLeastNumbers(arr, 2);
        for (int leastNumber : leastNumbers) {
            System.out.println(leastNumber);
        }
        int[] arr1 = getFeastNumbers(arr, 2);
        for (int leastNumber : arr1) {
            System.out.println(leastNumber);
        }

    }
}
